/**
 * 
 */
package com.gwcloud.leetcode.hot100;

/**
 * @ClassName   : Leetcode0085 
 * @author      : ganwei 
 * @date        : 2020年5月19日
 * @Description : Leetcode0085 最大矩形
 */
public class Leetcode0085 {
	/**
	 * -动态规划思路
	 */
    public int maximalRectangle(char[][] matrix) {
    	if(matrix.length == 0){
    		return 0;
    	}
    	int maxarea = 0;
    	int[][] dp = new int[matrix.length][matrix[0].length];
    	for(int i = 0; i < matrix.length; i++){
    		for(int j = 0; j < matrix[0].length; j++){
    			if(matrix[i][j] == '1'){
    				dp[i][j] = j == 0 ? 1 : dp[i][j-1] + 1;
    				int width = dp[i][j];
    				
                    for(int k = i; k >= 0; k--){
                        width = Math.min(width, dp[k][j]);
                        maxarea = Math.max(maxarea, width * (i - k + 1));
                    }

    			}
    		}
    	}
    	
    	return maxarea;
    }
    
    public static void main(String[] args){
    	
    }
}
